package listbyorder.access101_200.test116;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/8 9:16
 */
public class Solution1 {

    // 二叉树的遍历，太帅了
    public Node connect(Node root) {
        if (root == null || root.left == null) return root;
        // 定义三个指针
        Node pre = root;  // 上一个节点
        Node cur = null;  // 当前节点，我们维持一个pre.next = cur;
        Node start = pre;  // 记录每行的开始位置
        while (pre.left != null) {
            if (cur == null) {
                // cur == null 表示这行已经走到头了
                // 连线
                pre.left.next = pre.right;
                // 换下一行，更新节点
                pre = start.left;
                cur = start.right;
                start = pre;
            } else {
                pre.left.next = pre.right;
                pre.right.next = cur.left;

                pre = pre.next;
                cur = cur.next;
            }
        }
        return root;
    }
}
